package com.yz.mergesort;

public class SortTools {
    //创建一个临时数组处理数据
    private static Comparable[] yz;

    private static boolean less(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }

    public static void sortGet(Comparable[] a) {
        yz = new Comparable[a.length];
        int lo = 0, hi = a.length - 1;
        sort(a, lo, hi);
    }

    private static void sort(Comparable[] a, int lo, int hi) {
        //小小校验一下数据合理性
        if (lo >= hi)
            return;
        //分治之
        int mid = lo + (hi - lo) / 2;
        //递归之
        //左
        sort(a, lo, mid);
        //右
        sort(a, mid + 1, hi);
        //交给merge去实现归并
        merge(a, lo, mid, hi);
    }

    private static void merge(Comparable[] a, int lo, int mid, int hi) {
        //现在拿到两个有序的数组，将他们装到临时数组中然后复制给传入的a数组
        int index = lo, p1 = lo, p2 = mid + 1;
        while (p1 <= mid && p2 <= hi) {
            if(less(a[p1],a[p2])){
                yz[index++] = a[p1++];
            }else{
                yz[index++] = a[p2++];
            }
        }
        while (p1<=mid){
            yz[index++] = a[p1++];
        }
        while (p2 <= hi){
            yz[index++] = a[p2++];
        }
        //将yz传给a
        for (int i = lo; i <= hi; i++) {
            a[i]=yz[i];
        }
    }
}

